package com.zdp.leetcodeMiddle;

import java.util.ArrayList;
import java.util.List;

/*
* 题目描述：
* 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
* 答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = ""
输出：[]
示例 3：
输入：digits = "2"
输出：["a","b","c"]
提示：
0 <= digits.length <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 电话号码的字母组合_17 {
    public static void main(String[] args) {
        电话号码的字母组合_17 demo = new 电话号码的字母组合_17();
        List<String> strings = demo.letterCombinations("9");
        for(String temp:strings){
            System.out.println(temp);
        }
    }

    /*
    * 这种排列组合的 很多都可以用搜索+回溯来解决
    * 也可以直接用一个 Map 来存 数字和字母的映射关系
    * */
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if(digits.length() == 0){
            return result;
        }
        f(0,digits,new StringBuilder(),result);
        // 多层循环？
        return result;
    }

    public void f(int index,String digits,
                  StringBuilder temp,List<String> result){
        if(temp.length() == digits.length()){
            result.add(new String(temp));
            return ;
        }
        // 没有完成，继续添加元素
        int n = digits.charAt(index) - '0';
        int start = (n-2)*3;
        int length = 3;
        if(n == 7 || n==9){
            length = 4;
        }
        if(n>7){
            start++;
        }
        for(int i=start; i<start+length ; i++){
            int b = 'a'+i;
            temp.append((char)b);
            f(index+1,digits,temp,result);
            // 回溯，删除
            temp.deleteCharAt(temp.length()-1);
        }
    }
}
